/* Copyright 2014-2018 Rsyn
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "AbuReduction.h"
#include<string>

#include "contest_evaluation.h"

namespace ieda_contest {

/**
 * @brief Perform Timing-Driven Overlap Reducation. 
 * Designed to solve the overflow problem that exists in every GCell.
 * 
 */
void AbuReduction::runAbuReduction() {
	findOverlap();
	moveABUViolationCells();

  makeInstanceList();
  findOverlap();
  moveABUViolationCells();

} // end method

// -----------------------------------------------------------------------------

AbuReduction::AbuReduction(ContestDataManager* data_manager, QuadraticTDP* quadraticTDP)
 {
  _data_manager = data_manager;
  _qtdp = quadraticTDP;
  makeGCellInfo();
  makeInstanceList();
  _gcell_area_constraint = 1.0; 
}

void AbuReduction::makeGCellInfo() {
  // 限制坐标
  _core_max_x = _data_manager->get_idb_layout()->get_core()->get_bounding_box()->get_high_x();
  _core_max_y = _data_manager->get_idb_layout()->get_core()->get_bounding_box()->get_high_y();

  auto ssfs = _data_manager->get_idb_layout()->get_die()->get_bounding_box()->get_high_y();
  auto ssws = _data_manager->get_idb_layout()->get_die()->get_bounding_box()->get_high_y();

  std::map<std::string, int>& layer_name_to_idx_map = _data_manager->get_database()->get_layer_name_to_idx_map();

  std::set<int> single_gcell_x_span_set;
  std::set<int> single_gcell_y_span_set;
  for (idb::IdbGCellGrid* idb_gcell_grid : _data_manager->get_idb_layout()->get_gcell_grid_list()->get_gcell_grid_list()) {
    if (idb_gcell_grid->get_direction() == idb::IdbTrackDirection::kDirectionX) {
      single_gcell_x_span_set.insert(idb_gcell_grid->get_space());
      _max_gcell_id_x = idb_gcell_grid->get_num();
    } else if (idb_gcell_grid->get_direction() == idb::IdbTrackDirection::kDirectionY) {
      single_gcell_y_span_set.insert(idb_gcell_grid->get_space());
      _max_gcell_id_y = idb_gcell_grid->get_num();
    } else {
      std::cout << "[error] The direction of gcell grid is invaild!" << std::endl;
      exit(1);
    }
  }
  if (single_gcell_x_span_set.size() == 0) {
    std::cout << "[error] The x_gcell_grid is empty!" << std::endl;
    exit(1);
  }
  if (single_gcell_y_span_set.size() == 0) {
    std::cout << "[error] The y_gcell_grid is empty!" << std::endl;
    exit(1);
  }
  if (single_gcell_x_span_set.size() > 1) {
    std::cout << "[error] The x_gcell_grid is uneven!" << std::endl;
    exit(1);
  }
  if (single_gcell_y_span_set.size() > 1) {
    std::cout << "[error] The y_gcell_grid is uneven!" << std::endl;
    exit(1);
  }
  int single_gcell_x_span = *single_gcell_x_span_set.begin();
  int single_gcell_y_span = *single_gcell_y_span_set.begin();
  /**
   * single_gcell_x_span
   * single_gcell_y_span
   * single_gcell_area
   */
  _data_manager->get_database()->set_single_gcell_x_span(single_gcell_x_span);
  _data_manager->get_database()->set_single_gcell_y_span(single_gcell_y_span);
  _data_manager->get_database()->set_single_gcell_area(single_gcell_x_span * single_gcell_y_span);
  // layer_gcell_supply_map
  std::map<int, int>& layer_gcell_supply_map = _data_manager->get_database()->get_layer_gcell_supply_map();
  for (idb::IdbLayer* idb_layer : _data_manager->get_idb_layout()->get_layers()->get_layers()) {
    if (idb_layer->is_routing()) {
      idb::IdbLayerRouting* idb_routing_layer = dynamic_cast<idb::IdbLayerRouting*>(idb_layer);

      int prefer_pitch = 0;
      for (idb::IdbTrackGrid* idb_track_grid : idb_routing_layer->get_track_grid_list()) {
        idb::IdbTrack* idb_track = idb_track_grid->get_track();

        if (idb_routing_layer->get_direction() == idb::IdbLayerDirection::kHorizontal
            && idb_track->get_direction() == idb::IdbTrackDirection::kDirectionY) {
          prefer_pitch = idb_track->get_pitch();
        } else if (idb_routing_layer->get_direction() == idb::IdbLayerDirection::kVertical
                   && idb_track->get_direction() == idb::IdbTrackDirection::kDirectionX) {
          prefer_pitch = idb_track->get_pitch();
        }
      }
      if (idb_routing_layer->get_direction() == idb::IdbLayerDirection::kHorizontal) {
        layer_gcell_supply_map[layer_name_to_idx_map[idb_routing_layer->get_name()]] = (single_gcell_y_span / prefer_pitch);
      } else if (idb_routing_layer->get_direction() == idb::IdbLayerDirection::kVertical) {
        layer_gcell_supply_map[layer_name_to_idx_map[idb_routing_layer->get_name()]] = (single_gcell_x_span / prefer_pitch);
      }
    }
  }
}


void AbuReduction::makeInstanceList()
{
  _gcell_instance_map.clear();
  ieda::Stats to_status;
  std::vector<ContestInstance*> contest_instance_list = _data_manager->get_database()->get_ContestInstance_pvec();

  int total_area = 0;

  for (int i = 0; i < contest_instance_list.size(); i++) {
    ContestInstance* contest_instance = contest_instance_list[i];
  // int i = 0;
  // for (auto contest_instance : contest_instance_list) {
  //   i++;
    if (contest_instance == nullptr) {
      std::cout << "Debug contest_instance id = "<< i << std::endl;
      continue;
    }
    // ContestCoord coord(contest_instance->get_lower_point().get_x(), contest_instance->get_lower_point().get_y(), 0);
    ContestCoord coord(contest_instance->get_center_coord().get_x(), contest_instance->get_center_coord().get_y(), 0);

    // gcell
    auto gcell_cord = get_GCell_coord(coord);
    contest_instance->set_grid_coord(gcell_cord);
    contest_instance->set_area(contest_instance->get_width() * contest_instance->get_height());
    // contest_instance_list.push_back(contest_instance);

    _gcell_instance_map[gcell_cord]._instances.push_back(contest_instance);
    total_area += contest_instance->get_area();
  }
  double time_delta = to_status.elapsedRunTime();
  std::cout << "=============FUNC : makeInstanceList() Total Time Elapsed: " << time_delta << "s\n";

  // ieda::Stats to_status;
  // std::vector<ContestInstance>& contest_instance_list = _data_manager->get_database()->get_instance_list();

  // for (auto contest_instance : contest_instance_list) {
  //   auto coord = contest_instance.get_real_coord();
  //   // gcell
  //   auto gcell_cord = get_GCell_coord(coord);
  //   _gcell_instance_map[gcell_cord]._instances.push_back(&contest_instance);
  // }


  // double time_delta = to_status.elapsedRunTime();
  // LOG_INFO << "FUNC : makeInstanceList() Total Run Time: " << time_delta << "s";
}

ContestCoord AbuReduction::get_GCell_coord(const ContestCoord& coord)
{
  int single_gcell_x_span = _data_manager->get_database()->get_single_gcell_x_span();
  int single_gcell_y_span = _data_manager->get_database()->get_single_gcell_y_span();

  ContestCoord gcell_coord;
  gcell_coord.set_x((coord.get_x() > 0 ? coord.get_x() - 1 : coord.get_x()) / single_gcell_x_span);
  gcell_coord.set_y((coord.get_y() > 0 ? coord.get_y() - 1 : coord.get_y()) / single_gcell_y_span);
  // gcell_coord.set_layer_idx(coord.get_layer_idx());
  return gcell_coord;
}

/**
 * @brief Finding GCells with Overflow.
 * 
 */
void AbuReduction::findOverlap() {
  _abu_violation_cells.clear();
  ieda::Stats to_status;
  // gcell的最大面积限制
  int single_gcell_area = _data_manager->get_database()->get_single_gcell_area();

  int num = 0;
  for (auto& [gcell_coord, gcellinstans] : _gcell_instance_map) {
    num++;
    auto instance_list = gcellinstans._instances;
    gcellinstans._max_used_area = _gcell_area_constraint * single_gcell_area;
    std::vector<std::tuple<ContestInstance*, std::tuple<float, ContestCoord>>> abu_violation_cells;
    int gcell_used_area = 0;
    for (auto& instance : instance_list) {
      gcell_used_area += instance->get_area();
      // 获得单元的slack
      double slack = _qtdp->getCellWorstSlack1(instance);
      // double slack = 0;
      abu_violation_cells.push_back(std::make_tuple(instance, std::make_tuple(slack, gcell_coord)));
    }
    _gcell_instance_map[gcell_coord]._used_area = gcell_used_area;
    if (gcell_used_area > _gcell_area_constraint*single_gcell_area) {
      // std::cout << "Overlap GCell: (" << gcell_coord.get_x() << ", " << gcell_coord.get_y() << "), used area " << gcell_used_area
      //           << ", max usable area " << single_gcell_area << std::endl;
      _abu_violation_cells.insert(_abu_violation_cells.end(), abu_violation_cells.begin(), abu_violation_cells.end());
    }
  }

  // 根据slack对_abu_violation_cells进行排序
  // sort();
  std::sort(_abu_violation_cells.begin(), _abu_violation_cells.end(),
            [=](std::tuple<ContestInstance*, std::tuple<float, ContestCoord>> cell1, 
                std::tuple<ContestInstance*, std::tuple<float, ContestCoord>> cell2)
            {
              double slack1 = std::get<0>(std::get<1>(cell1));
              double slack2 = std::get<0>(std::get<1>(cell2));
              return (slack1 < slack2);
            });
  _abu_violation_cells.resize(_abu_violation_cells.size());
  double time_delta = to_status.elapsedRunTime();
  std::cout << "=============FUNC : findOverlap() Total Run Time Elapsed: " << time_delta << "s\n";

}

/**
 * @brief Moving cells within a GCell according to its timing slacks.
 * 
 */
void AbuReduction::moveABUViolationCells() {
  int single_gcell_area = _data_manager->get_database()->get_single_gcell_area();
  //   std::vector<std::tuple<ContestInstance, DBUxy>> movedCells;
  // 	movedCells.reserve(_abu_violation_cells.size());
  int success = 0;
  int fail = 0;
  for (std::tuple<ContestInstance*, std::tuple<double, ContestCoord>> tp : _abu_violation_cells) {

    // if (_exit) { return; }

    ContestInstance* cell = std::get<0>(tp);
    double slack = std::get<0>(std::get<1>(tp));
    ContestCoord gcell = std::get<1>(std::get<1>(tp));
    int used_area = _gcell_instance_map[gcell]._used_area;

    // 检查一下当前GCell是否还存在overlap
    if (!_gcell_instance_map[gcell].isViolation()) {
      continue;
    }

    // 找当前cell附近最近的不违例的位置
    auto best_moved = findNearstNonviolationLocation(cell, gcell);
    auto best_removed_gcell = std::get<0>(best_moved);
    int best_moved_x = std::get<0>(std::get<1>(best_moved));
    int best_moved_y = std::get<1>(std::get<1>(best_moved));

    if (!_qtdp->moveCell(cell, best_moved_x, best_moved_y)) {
      fail++;
    } else {
      success++;
      _exit = true;
      // std::cout << "Debug move instance : " << cell->get_name() << " to location (" << best_moved_x << ", " << best_moved_y << ") successful.\n";
      // 更新gcell_instance_map
      _gcell_instance_map[gcell]._used_area -= cell->get_area();
      _gcell_instance_map[best_removed_gcell]._used_area += cell->get_area();
    }
  }
}


std::vector<ContestCoord> AbuReduction::getNeighbours(ContestCoord p, int radius)
{
  std::vector<ContestCoord> neighbours;

  for (int dx = -radius; dx <= radius; ++dx) {
    for (int dy = -radius; dy <= radius; ++dy) {
      if (dx == 0 && dy == 0) {
        continue;  // Skip the center point
      }
      int newX = p.get_x() + dx;
      int newY = p.get_y() + dy;
      if (newX >= _max_gcell_id_x || newY >= _max_gcell_id_y)
        continue;
      if (newX < 0 || newY < 0)
        continue;
      neighbours.push_back(ContestCoord(newX, newY));
    }
  }
  return neighbours;
}

std::tuple<ContestCoord, std::tuple<int, int>> AbuReduction::findNearstNonviolationLocation(ContestInstance* contest_inst, ContestCoord gcell)
{
  // gcell的最大面积限制
  int single_gcell_area = _data_manager->get_database()->get_single_gcell_area();  // gcell的最大面积限制

  int single_gcell_x_span = _data_manager->get_database()->get_single_gcell_x_span();
  int single_gcell_y_span = _data_manager->get_database()->get_single_gcell_y_span();

  // auto inst_loc = contest_inst->get_real_coord();
  // auto inst_loc = contest_inst->get_lower_point();
  auto inst_loc = contest_inst->get_center_coord();
  int inst_x = inst_loc.get_x();
  int inst_y = inst_loc.get_y();

  int inst_center_x = contest_inst->get_width();
  int inst_center_y = contest_inst->get_height();

  int maxRadius = 2;

  int best_remove_dist = 1E+30F;
  bool find = 0;

  // 哪个方向，哪个gcell
  RelativeDirection best_removed_direct;
  ContestCoord best_removed_gcell;

  // 移到哪个位置
  int best_moved_x;
  int best_moved_y;

  for (int radius = 1; radius <= maxRadius; ++radius) {
    // std::cout << "Traversing ring at radius " << radius << ":" << std::endl;

    auto gcell_ring_neighbor = getNeighbours(gcell, radius);
    for (auto neighbor_coord : gcell_ring_neighbor) {
      // std::cout << "(" << neighbor_coord.get_x() << ", " << neighbor_coord.get_y() << ")" << std::endl;
      if ((_gcell_instance_map[neighbor_coord]._used_area + contest_inst->get_area()) < _gcell_area_constraint * single_gcell_area) {
        // contest_inst和这个gcell最近的距离
        // int distance = std::abs(inst_loc.get_x() - coord.get_x()) + std::abs(inst_loc.get_y() - coord.get_y());
        auto which_direction = whichDirection(neighbor_coord, gcell);
        switch (which_direction) {
          case RelativeDirection::kUp: {
            // 在上方只需移动沿着Y轴移动
            int y = neighbor_coord.get_y() * single_gcell_y_span;
            int remove_dist = std::abs(inst_y - y);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kUp;
              best_removed_gcell = neighbor_coord;
              best_moved_x = inst_x;
              best_moved_y = y < (_core_max_y - 1) ?  y + 1 : _core_max_y;
              // best_moved_y += inst_center_y;
            }
            break;
          }
          case RelativeDirection::kDown: {
            // 在下方只需移动沿着Y轴移动
            int y = (neighbor_coord.get_y() + 1) * single_gcell_y_span;
            int remove_dist = std::abs(inst_y - y);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kDown;
              best_removed_gcell = neighbor_coord;
              best_moved_x = inst_x;
              best_moved_y = y < 1 ? 1 : y - 1;
              // best_moved_y -= inst_center_y;
            }
            break;
          }
          case RelativeDirection::kLeft: {
            // 在左侧只需移动沿着X轴移动
            int x = (neighbor_coord.get_x() + 1) * single_gcell_x_span;
            int remove_dist = std::abs(inst_x - x);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kLeft;
              best_removed_gcell = neighbor_coord;
              best_moved_x = x < 1 ? 1: x - 1;
              best_moved_y = inst_y;
              // best_moved_x -= inst_center_x;
            }
            break;
          }
          case RelativeDirection::kRight: {
            // 在右侧只需移动沿着X轴移动
            int x = neighbor_coord.get_x() * single_gcell_x_span;
            int remove_dist = std::abs(inst_x - x);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kRight;
              best_removed_gcell = neighbor_coord;
              best_moved_x = x < (_core_max_x - 1) ?  x + 1 : _core_max_x;
              best_moved_y = inst_y;
              // best_moved_x += inst_center_x;
            }
            break;
          }
          case RelativeDirection::kUp_left: {
            int x = (neighbor_coord.get_x() + 1) * single_gcell_x_span;
            int y = neighbor_coord.get_y() * single_gcell_y_span;
            int remove_dist = std::abs(inst_x - x) + std::abs(inst_y - y);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kUp_left;
              best_removed_gcell = neighbor_coord;
              best_moved_x = x < 1 ? 1: x - 1;
              best_moved_y = y < (_core_max_y - 1) ?  y + 1 : _core_max_y;
              // best_moved_x -= inst_center_x;
              // best_moved_y += inst_center_y;
            }
            break;
          }
          case RelativeDirection::kUp_right: {
            int x = neighbor_coord.get_x() * single_gcell_x_span;
            int y = neighbor_coord.get_y() * single_gcell_y_span;
            int remove_dist = std::abs(inst_x - x) + std::abs(inst_y - y);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kUp_right;
              best_removed_gcell = neighbor_coord;
              best_moved_x = x < (_core_max_x - 1) ?  x + 1 : _core_max_x;
              best_moved_y = y < (_core_max_y - 1) ?  y + 1 : _core_max_y;
              // best_moved_x += inst_center_x;
              // best_moved_y += inst_center_y;
            }
            break;
          }
          case RelativeDirection::kDown_left: {
            int x = (neighbor_coord.get_x() + 1) * single_gcell_x_span;
            int y = (neighbor_coord.get_y() + 1) * single_gcell_y_span;
            int remove_dist = std::abs(inst_x - x) + std::abs(inst_y - y);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kDown_left;
              best_removed_gcell = neighbor_coord;
              best_moved_x = x < 1 ? 1: x - 1;
              best_moved_y =y < 1 ? 1: y - 1;
              // best_moved_x -= inst_center_x;
              // best_moved_y -= inst_center_y;
            }
            break;
          }
          case RelativeDirection::kDown_right: {
            int x = neighbor_coord.get_x() * single_gcell_x_span;
            int y = (neighbor_coord.get_y() + 1) * single_gcell_y_span;
            int remove_dist = std::abs(inst_x - x) + std::abs(inst_y - y);
            if (remove_dist < best_remove_dist) {
              best_remove_dist = remove_dist;
              find = 1;
              best_removed_direct = RelativeDirection::kDown_right;
              best_removed_gcell = neighbor_coord;
              best_moved_x = x < (_core_max_x - 1) ?  x + 1 : _core_max_x;
              best_moved_y = y < 1 ? 1: y - 1;
              // best_moved_x += inst_center_x;
              // best_moved_y -= inst_center_y;
            }
            break;
          }
        }
      }
    }
    // 第一圈有找到就直接停止
    if (find) {
      return std::make_tuple(best_removed_gcell, std::make_tuple(best_moved_x, best_moved_y));
    }
  }
  return std::make_tuple(best_removed_gcell, std::make_tuple(best_moved_x, best_moved_y));
}

/*
 @brief a在b的什么方向
*/
RelativeDirection AbuReduction::whichDirection(ContestCoord a, ContestCoord b) {
  if (a.get_x() == b.get_x()) {
    if (a.get_y() > b.get_y()) {
      return RelativeDirection::kUp;
    } else {
      return RelativeDirection::kDown;
    }
  } else if (a.get_y() == b.get_y()) {
    if (a.get_x() > b.get_x()) {
      return RelativeDirection::kRight;
    } else {
      return RelativeDirection::kLeft;
    }
  } else if (a.get_x() > b.get_x()) {
    if (a.get_y() > b.get_y()) {
      return RelativeDirection::kUp_right;
    } else {
      return RelativeDirection::kDown_right;
    }
  } else {
    if (a.get_y() > b.get_y()) {
      return RelativeDirection::kUp_left;
    } else {
      return RelativeDirection::kDown_left;
    }
  }
}


} // end namescape